import collections
from typing import List


class Solution:
    def maxGroupNumber(self, tiles: List[int]) -> int:
        count = collections.Counter(tiles)
        nums = sorted(count.keys())

        ans = 0
        now = []
        for i in range(len(nums)):
            if now:
                if nums[i] > nums[i - 1] + 1:  # 不连续的情况
                    ans += self.count_continuation(now)
                    now = []
            now.append(count[nums[i]])
        ans += self.count_continuation(now)
        return ans

    def count_continuation(self, nums):
        """连续数列计算：count=每一个数字的频数"""
        # print("连续数列:", nums)

        # 连续数列不足3个数的情况：只需要考虑刻子
        if len(nums) < 3:
            return sum(num // 3 for num in nums)

        dp1 = {(nums[0], nums[1]): 0}

        # 连续数列大于等于3个的情况：每一步结合前2个，考虑尽可能在得出最多组的结果下，保留最多的牌（优先最后一个，然后优先倒数第二个）
        for i in range(2, len(nums)):
            dp2 = {}
            for n1, n2 in dp1:
                n3 = nums[i]
                s = min(n1, n2, n3)
                for j in range(max(0, s - 9), s + 1):  # 需要考虑比最大刻字少9个的情况
                    v = dp1[(n1, n2)] + j + (n1 - j) // 3
                    if (n2 - j, n3 - j) not in dp2 or v > dp2[(n2 - j, n3 - j)]:
                        dp2[(n2 - j, n3 - j)] = v
            dp1 = dp2

        ans = 0
        for (n1, n2), v in dp1.items():
            ans = max(ans, v + n1 // 3 + n2 // 3)

        return ans


if __name__ == "__main__":
    print(Solution().maxGroupNumber([2, 2, 2, 3, 4]))  # 1
    print(Solution().maxGroupNumber([2, 2, 2, 3, 4, 1, 3]))  # 2

    # 测试用例18/72 : 2
    print(Solution().maxGroupNumber([1, 2, 2, 2, 3, 4, 5]))  # 2

    # 测试用例22/72 : 13
    print(Solution().maxGroupNumber(
        [1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 10, 10, 10,
         10, 11, 11, 11, 12]))
